package com.zzh.dp;
//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
// 示例:
//
// 输入: [-2,1,-3,4,-1,2,1,-5,4],
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
//
//
// 进阶:
//
// 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
// Related Topics 数组 分治算法 动态规划
// 👍 2131 👎 0
public class No53_maxSubArray {
    public static void main(String[] args) {
        No53Solution solution=new No53Solution();
        int i = solution.maxSubArray02(new int[]{-2,1,-3,4,-1,2,1,-5,4});
        System.out.println(i);
    }
}
class No53Solution {
    //分治法
    public int dac(int[] nums,int begin,int end){
        int mid=(begin+end)/2;
        if (begin>=end){
           return nums[end];
        }

        int sumLeft=dac(nums,begin,mid);
        int sumRight=dac(nums,mid+1,end);
        int sum=0;
        int max0=Integer.MIN_VALUE;
        for (int i=mid;i>=begin;i--){
//            if (sum+nums[i]>max0){
//                max0=sum+nums[i];
//
//            }
            sum+=nums[i];
            max0=Math.max(sum,max0);

        }
        int max1=Integer.MIN_VALUE;
        sum=0;
        for (int i=mid+1;i<=end;i++){
            if (sum+nums[i]>max1){
                max1=sum+nums[i];
            }
            sum+=nums[i];
        }
        int sumMid=max0+max1;
        return Math.max(sumLeft,Math.max(sumMid,sumRight));

    }
    public int maxSubArray02(int[] nums){
        return dac(nums,0,nums.length-1);
    }
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(Math.max(nums[0], nums[1]), nums[0] + nums[1]);
        }
        int[] sum = new int[nums.length + 1];
        sum[0] = 0;
//        sum[1] = nums[0];
        for (int i = 0; i < nums.length; i++) {
            sum[i+1] = sum[i] + nums[i];
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < sum.length; i++) {
            if (sum[i] < min) {
                min = sum[i];
                max=Math.max(max,nums[i%nums.length]);
            } else if (sum[i] - min > max) {
                max = sum[i] - min;
            }
        }
        return max;
    }
}